/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/kth-largest-element
   @Language: C++
   @Datetime: 16-02-09 05:55
   */

class Solution {
	int partition(vector<int> &nums, int begin, int end){
		int i=begin, j=end-1, key;
		if (i<0 || i>=j) return i;
		for(key=nums[i]; i<j;){
			for(; i<j && nums[j]>=key; --j);
			nums[i] = nums[j];
			for(; i<j && nums[i]<=key; ++i);
			nums[j] = nums[i];
		}
		nums[i] = key;
		return i;
	}

public:
	/*
	 * param k : description of k
	 * param nums : description of array and index 0 ~ n-1
	 * return: description of return
	 */
	int kthLargestElement(int k, vector<int> nums) {
		// write your code here
		k = nums.size()-k;  // trans kth largest to (n-k)-th smallest
		for(int i=0, j=nums.size(), pos=-1; pos!=k;){
			pos = partition(nums,i,j);
			i = (pos<k ? pos+1 : i);
			j = (pos>k ? pos : j);
		}
		return nums[k];
	}
};
